public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();

        // String s = "abcbdda";
        // System.out.println(test.checkPartitioning(s));

        String s = "abbbnb";
        System.out.println(test.minCut(s));
    }

    public boolean checkPartitioning(String s) {
        /**
         * 分割回文串
         * 题目要求：只要将目标字符串分割为3个非空的回文字符串即可
         * 状态表示：
         *  dp[i][j]表示以i下标元素为开始，j下标元素为结尾的子字符串，是否是回文子串，规定i<=j
         * 状态转移方程：
         *  if(s.charAt(i) == s.charAt(j)) {
         *      if(i+1 >= j || dp[i+1][j-1]);
         *  }
         * 初始化：
         *  已知i<=j，并且当i==j时会自动判断，只有i<j时才会使用dp[i+1][j-1]，因此无需初始化
         * 填表顺序：
         *  从下到上，从左到右
         * 返回值：
         *  需要使用两种算法
         * */
        // 1 预处理
        int n = s.length();
        // 2 创建dp表
        boolean[][] dp = new boolean[n][n];
        // 3 初始化
        // 4 填表
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    if(i+1 >= j || dp[i+1][j-1]) {
                        dp[i][j] = true;
                    }
                }
            }
        }
        // 5 执行题目逻辑
        // - 固定第一个值，寻找后续值
        for(int i = 0; i < n-2; i++) {
            // <1> 固定第一个回文字符串
            if(dp[0][i]) {
                for(int j = i+1; j < n-1; j++) {
                    // <2> 在剩余空间中找到剩下两个回文字符串
                    if(dp[i+1][j] && dp[j+1][n-1]) {
                        return true;
                    }
                }
            }
        }
        // 6 返回值
        return false;
    }

    public int minCut(String s) {
        /**
         * 分割回文串-最少分割次数
         * 解题思路：
         *   1，先找到所有回文字符串
         *   2，计算解题逻辑
         * 状态表示：
         *  dp[i][j]表示以i下标元素为结尾的字符串，分割成回文子串的最少分割次数
         * 状态转移方程：
         *  if(dp[j][i]) {
         *      if(j == 0) {
         *          dpp[i] = 0;
         *      }
         *      if(dpp[j-1]) {
         *          dpp[i] = Math.min(dpp[i], dpp[j-1] + 1);
         *      }
         *  }
         * 初始化：
         *  由于在状态转移方程中，已经对越界情况进行处理，故无需初始化
         * 填表顺序：
         *  从左至右
         * 返回值：
         *  dpp[n-1]
         * */

        // 1 预处理
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    if(i+1 >= j || dp[i+1][j-1]) {
                        dp[i][j] = true;
                    }
                }
            }
        }
        // 2 创建dp表
        int[] dpp = new int[n];
        // 3 初始化
        for(int i = 1; i < n; i++) {
            dpp[i] = i;
        }
        // 4 填表
        for(int i = 0; i < n; i++) {
            // -提高代码运行效率
            if(dp[0][i]) {
                dpp[i] = 0;
            } else {
                for(int j = i; j >= 0; j--) {
                    if(dp[j][i]) {
                        dpp[i] = Math.min(dpp[i], dpp[j-1] + 1);
                    }
                }
            }
        }
        // 5 返回值
        return dpp[n-1];
    }
}
